/*
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <hash_map>
#include <set>
#include <vector>
#include <Stack>
#include <iostream>
#include <sstream>
using namespace std;

struct ListNode{
	int val;
	ListNode *next;
	ListNode(int x):val(x),next(NULL){}
};

ListNode * generateList(int a[],int len){
	ListNode *head=NULL,*q;
	for(int i=0;i<len;i++){
		ListNode *p=new ListNode(a[i]);
		if(!head){
			head=p;
			q=p;
		}else{
			q->next=p;
			q=p;
		}
	}
	return head;
}
void print(ListNode *p){
	while(p){
		cout<<p->val<<"->";
		p=p->next;
	}
	cout<<endl;
}
ListNode* partition(ListNode* head, int x) {
	ListNode *p,*q,*w,*pre=NULL,*tmp;
	w=head;
	while(w&&w->val<x){
		p=pre=w;
		w=w->next;		
	}
	while(w){
		if(w->val<x){
			tmp=w;
			if(pre==NULL){
				p->next=w->next;
				w=w->next;
				tmp->next=head;
				head=pre=tmp;
			}else{
				p->next=w->next;
				w=w->next;
				tmp->next=pre->next;
				pre->next=tmp;
				pre=tmp;
			}
			continue;
		}
		p=w;
		w=w->next;
	}
	return head;
}
int main(){
	int a[]={1,3,-1,5,2,1};
	ListNode *p=generateList(a,sizeof(a)/sizeof(int));
	print(p);
	ListNode *q=partition(p,3);
	print(q);
	cout<<endl;
	system("pause");
}
*/